package com.leetcode.二叉树;

/**
 * 给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
 * 
 * @author LZF
 *
 */
public class L226翻转二叉树 {
	/**
	 * 用递归，也就是深搜，前后序可以实现，唯独中序遍历不行。
	 * 因为，如果使用中序遍历，从代码中可以看出，先深搜左子树，中间是转换，再深搜右子树
	 * 导致的结果就是，中间转换之后，再深搜右子树，有可能右子树变为了原来的左子树，此时右子树再转换，又变为右子树自己
	 * 所以中序遍历，会有可能导致一些节点转换了两次。
	 */
	public TreeNode invertTree(TreeNode root) {
		dfsPre(root);
		return root;
	}
	public void dfsPre(TreeNode node) {
		if(node == null) return ;
		swap(node);//swap放在这里是前序
		dfsPre(node.left);
//		swap(node);//swap放在这里是中序
		dfsPre(node.right);
//		swap(node);//swap放在这里是后序
	}
	public void swap(TreeNode node) {
		TreeNode temp = node.left;
		node.left = node.right;
		node.right = temp;
	}
	
	//树的定义
	public class TreeNode {
		int val;
		TreeNode left;
		TreeNode right;

		TreeNode() {
		}

		TreeNode(int val) {
			this.val = val;
		}

		TreeNode(int val, TreeNode left, TreeNode right) {
			this.val = val;
			this.left = left;
			this.right = right;
		}
	}
}
